Nowadays, the radio communication devices such as base stations are increasingly employing the dual or even multiple processors so as to improve the processing efficiency, in which the signal processing is usually performed through spawning multiple communication schedulable units (CSUs) running in parallel to achieve high performance. However, unlike the common parallel processing environment for example in the traditional desktop Operation System (OS), there are still several challenges in the radio communication environment which need be carefully handled:
1. Synchronization between CSUs
Generally, in order that the CSUs of the same owner can access the same data source simultaneously, the semaphore mechanism will be involved to guarantee the data integrity by reinforcing the multiple CSUs serial execution. However, it may cause unnecessary CSU context switch. So in radio communication environment it needs to consider another mechanism to guarantee the synchronization between CSUs.
2. Controlling of the processor resources consumption
In the radio communication environment, it usually adopts non-preemption scheduling to avoid unnecessary context switch, which however introduces a side effect that once a processor is occupied by a low priority CSU, the processor can not be released unless the low priority CSU aborts the processor by itself. Thus it is needed to limit the processor usages to avoid the excessive consumption by those low priority CSUs.
3. Affinity among the CSUs
The normal CSU scheduling criteria can be based on the priority or time stamp of the CSUs. However, the affinity among the CSUs is also a factor to be considered due to overhead of code and data cache missing. Generally, the affinity means a kind of bundling relationship between an executive unit (e.g. CSU) and a processor for some purposes. For example, the executive units may access the same data context and be intended to be processed by the same processor. In this way, when the processor successively processes the executive units with affinity, such data context stored in the cache can be reused without involving switching of code in the cache. If a CSU has affinity with currently executing CSU, for example this CSU and the currently executing CSU belong to the same owner, and accordingly they may access the same data context, then although this CSU is created later than another earlier CSU of other owners waiting to be processed, it can be scheduled prior to the earlier one as long as the CSU is close enough to the current executing CSU on creation time stamp (e.g. the time interval is smaller than a threshold), since the affinity may alleviate the overhead of code and data cache missing.
Currently, there are two known CSU scheduling solutions in the radio communication environment: CSU-based solution and owner-based solution.
As illustrated in FIG. 1, the CSU-based solution queues all the ready CSUs in a waiting list. Once a processor is available, it can fetch the first CSU for execution. However, as mentioned before, the CSU at list head (beginning of the list) may not be allowed to run due to synchronization if another CSU under the same owner is running. So it needs to go through the list from head to check subsequent CSUs one by one until the first CSU of an idle owner is found. Then the CSU is unlinked from the list and executed on the processor. Next time when another processor is idle, the above browse procedure is repeated again from the head. In other word, the CSU scheduling involves a linear search on the waiting list, which causes the searching time complexity of O(N) indicating a linear running time, which is low efficiency in the radio communication environment that has higher requirement in terms of the real-time. Furthermore, since the CSU-based solution adopts linear search along the list to find an appropriate CSU to schedule, to avoid too much searching overhead, it stops once an appropriate CSU is met and does not go further in the list. In such a way, only the time order of the CSUs is considered while the affinity among the CSUs is neglected, which may cause frequent switching of code in the cache if a CSU under a different owner is dispatched.
By contrast, the owner-based solution, as illustrated in FIG. 2, always successively schedules the CSUs under a single owner for a processor, and the CSUs under other owners will not be scheduled until all the CSUs under the single owner have been processed. As indicated, the owner-based solution does not involve the linear search in the CSU scheduling, however it can only see the CSUs under the same owner without global view of CSUs under different owners. In other words, contrary to the CSU-base solution, it only considers the affinity among the CSUs while neglecting the time order of the CSUs. So it always finishes all CSUs under one owner before considering the CSUs under others, which may cause unbalanced resources consumption among owners. Extremely, if a running owner always has incoming CSUs, the CSUs of other owners can't be scheduled.
In addition, actually some CSUs under the same owner may also be independent of each other, since they access the different parts of same data context. They still can be dispatched on multiple processors to run in parallel. In this case, those independent CSUs need to be grouped to different “sub-owners”. However both of the current solutions inhibit such mode and enforce that all the CSUs under the same owner must be run in serial due to the impossibility of data orthogonal division among multiple “sub-owners”. There are “always” some CSUs stepping into other sub-owners' zone, in other words, the CSU under one owner may access the part of data context used by the other owners, thereby block the CSU execution in other, even all, sub-owners.